package ext;

import def.TreeNode;

import java.util.Stack;

/**
 * 二叉树非递归遍历
 */
public class BinaryTreeTraversal {

    public static String preOrderTraversal(TreeNode root) {
        String res = "";
        Stack<TreeNode> stk = new Stack<TreeNode>();
        stk.push(root);
        while (!stk.empty()) {
            TreeNode top = stk.pop();
            res += top.val;
            if (top.right != null)
                stk.push(top.right);
            if (top.left != null)
                stk.push(top.left);
        }
        return res;
    }

    public static String inOrderTraversal(TreeNode root) {
        String res = "";
        Stack<TreeNode> stk = new Stack<TreeNode>();
        TreeNode ptr = root;//指向一颗未处理的子树
        while (!stk.empty() || ptr != null) {
            if (ptr != null) {
                stk.push(ptr);
                ptr = ptr.left;
            } else {
                ptr = stk.pop();
                res += ptr.val;
                ptr = ptr.right;
            }
        }

        return res;
    }

    public static String postOrderTraversal(TreeNode root) {
        return "";
    }

    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        TreeNode n6 = new TreeNode(6);
        TreeNode n7 = new TreeNode(7);

        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        n3.right = n6;

        System.out.println("先序遍历");
        System.out.println(preOrderTraversal(n1));

        System.out.println("中序遍历");
        System.out.println(inOrderTraversal(n1));
    }
}
